package com.链表;

/**
 * 请判断一个链表是否为回文链表。
 *
 * 示例 1:
 *
 * 输入: 1->2
 * 输出: false
 * 示例 2:
 *
 * 输入: 1->2->2->1
 * 输出: true
 */
public class 回文链表 {
    static class Solution {
        /**
         * 1.采用快慢指针截取出前后段
         * 2.反转后段
         * 3.对比前后段
         * @param head
         * @return
         */
        public static boolean isPalindrome(ListNode head) {
            if(head==null || head.next == null){
                return true;
            }
            ListNode node = new ListNode(-1);
            node.next = head;
            ListNode slow = node;
            ListNode fast  = node;

            //慢指针走一步，快指针走两步，快指针走完的时候慢指针正好走到中间
            while ( fast != null && fast.next != null ){
                slow = slow.next;
                fast = fast.next.next;

            }
            //后半段
            fast = slow.next;
            //前半段
           slow.next = null;
           slow = node.next;
            //反转
            ListNode reversal = null;
            //反转后半段
            //反转的逻辑很饶脑壳，截取出头指针，加入到反转中

            while(fast != null){
                //临时链表
                ListNode tmp = fast.next;
                //截取头指针
                fast.next = reversal;
                //加入到反转
                reversal = fast;
                fast = tmp;
            }

            //对比前后值，当为奇数时，以后段为准
            while (reversal != null){
                if(slow.val != reversal.val){
                    return false;
                }
                slow = slow.next;
                reversal = reversal.next;
            }
            return true;




        }
        public static boolean IsPalindrome(ListNode head) {
            // 边界条件：空链表或只有一个节点的链表
            if (head == null || head.next == null) {
                return true;
            }

            ListNode dummyNode = new ListNode(-1);
            dummyNode.next = head;
            ListNode slow = dummyNode;
            ListNode fast = dummyNode;

            // 慢指针一次走一步，快指针一次走两步，当快指针走到终点，慢指针刚好处于中点位置
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }

            // fast指针置于下半段链表的起点
            fast = slow.next;
            // 断开前后两个链表
            slow.next = null;
            // slow指针置于前半段链表的起点
            slow = dummyNode.next;

            // 反转后半段链表
            ListNode pre = null; // 保存指针前一节点的信息，用于反转
            while (fast != null) {
                ListNode nextTemp = fast.next;
                fast.next = pre;
                pre = fast;
                fast = nextTemp;
            }

            // 前后半链表逐一比较，当链表长度为奇数时前半段链表长度比后半段多1，所以以后半段为准
            while (pre != null) {
                if (slow.val != pre.val) {
                    return false;
                }
                slow = slow.next;
                pre = pre.next;
            }
            return true;
        }


    }

    public static void main(String[] args) {
        System.out.println(Solution.IsPalindrome(new ListNode(new int[]{1,2,22,2,1})));
    }
}
